/********************************************************************
* Name: InstructionReorderFilter.cpp
*
* Description:
*	reorder the vinst in a basic block
*
* History:
*   Create: suntingtao 2009-03-06
*
********************************************************************/

#include "crossbit/InstructionReorderFilter.h"
#include "crossbit/UTIL.h"
#include <iterator>
#include <algorithm>
#include "queue"
#include "vector"

using namespace crossbit;

XTUint32 InstructionReorderFilter::run(VBlock *vb)
{
//	vb -> print( std :: cout );
    VBlock::vb_iterator it = vb->begin(); 
	int n = vb -> size();
	std::queue<XTInt32> dep_list[n];
	// the last memory access vinst index in the former vblock
	XTInt32 last_mem_acc = -1;
	// last_dep[i] = j , means the former vinst "i" denpends on the new vinst "j" in the new vinst list.
	XTInt32 last_dep[n]; 
    UTIL::XTMemset( last_dep , -1 , sizeof(XTInt32) * n  );
	// index[i] = j : means the former vinst "i" is put in the index "j" in the new vinst list
	XTInt32 index[n];
	const XTInt32 VREG_NUM = 200;
	// the last definition of the vreg in the former vinst
	XTInt32 last_def[VREG_NUM];
	std::vector<XTInt32> vreg_use[VREG_NUM];
	// all vreg are not defined
    UTIL::XTMemset( last_def , -1 , sizeof(XTInt32) * VREG_NUM );
	// represent if the former vinst put back 
	bool  reset[n];
    UTIL::XTMemset( reset , 0 , sizeof(bool) * n );
	VInst* vinst[n];
	for( XTInt32 i = 0 ; i < n - 1 ; i++ ) {
		vinst[i] = *it;
		it++;
		Opkind opkind = vinst[i] -> getOpkind();
		if( opkind == OPK_MEMORYACCESS ) {
			if( last_mem_acc != -1 ) {
				dep_list[i].push( last_mem_acc );
			}
			last_mem_acc = i ;
		}
		for( XTInt32 j = 1 ; j <= vinst[i] -> getOperandNum() ; j++ ){
			Operand opr = vinst[i] -> getOperand( j );
			switch ( opr.type ) {
				case Operand::VREG_USE  : 
											if( last_def[opr.reg] >= 0 ) 
												dep_list[i].push(last_def[opr.reg]);
											vreg_use[opr.reg].push_back(i);
											break;
				case Operand::VREG_DEF  :  if( last_def[opr.reg] >= 0 )
												dep_list[i].push(last_def[opr.reg]);
										   for( XTInt32 k = 0 ; k < vreg_use[opr.reg].size() ; k++ ) {
										   		if( vreg_use[opr.reg][k] != i ) {
													dep_list[i].push(vreg_use[opr.reg][k]);
												}
											}
											vreg_use[opr.reg].clear();
											last_def[opr.reg] = i;
											break;
				default :					break;
			}
		}
	}
	XTInt32 best_index;
	for( XTInt32 i = 0 ; i < n - 1; i++ ) {
		best_index = -1;
		for( XTInt32 j = 0 ; j < n - 1 ; j ++ ){
			if( reset[j] ) {
				continue;
			}
			while( dep_list[j].empty() == false && reset[ dep_list[j].front() ] == true ){
				   XTInt32 k = dep_list[j].front();
				   if( index[k] > last_dep[j] ) last_dep[j] = index[k]; 
				   dep_list[j].pop();
			}
			if( dep_list[j].empty() ) {
				XTInt32 temp_dis = last_dep[j];

				if( temp_dis == -1 ) {
					temp_dis = i - 2;
				}
		// */
				if( best_index == -1 || last_dep[best_index] != -1 && temp_dis < last_dep[best_index]) {
					best_index = j;
				}

			}
		}
		assert( best_index != -1 && "one vinst must be choice!\n");
	    vb -> setVbIlist( i , vinst[best_index] );	
		reset[best_index] = true;
		index[best_index] = i;
	}
	/*
    printf("\n");
	vb -> print( std::cout );
	char xx[100];
	scanf("%s" , xx );
	*/
	return 1;
}



		


